package com.二叉树的下一个节点;

public class Solution {

	public TreeLinkNode GetNext(TreeLinkNode pNode) {
		if (pNode.right == null) {
			if (pNode.next == null)
				return null;
			else if (pNode == pNode.next.left)// 这个点是叶子节点，并且是父亲节点的左子树
				return pNode.next;
			else {// 这个点是叶子节点，并且是父节点的右子树
				//那么就要向上遍历，并且找一个节点是其父节点的左子节点
				//那么这个节点的父节点就是返回的值
				while (pNode.next!=null) {
					if(pNode==pNode.next.left) {
						return pNode.next;
					}
					pNode = pNode.next;
				}
				return null;//如果返回到根节点了还没找到，就返回null
			}
		} else {
			TreeLinkNode rNode = pNode.right;
			while(rNode.left!=null) {
				rNode = rNode.left;
			}
			return rNode;
		}
	}

	
}
